//
// Created by Win10 on 2022/11/15.
//

#include<iostream>
#include "tb_tree.h"

using namespace std;

static ThreadNode *pre= nullptr;    //指向当前访问节点的前驱


//初始化树
void InitTree(ThreadTree &T) {
    ElemType ch;
    cin >> ch;
    if (ch == '#') {
        T = nullptr;
    } else {
        T = (ThreadNode *) malloc(sizeof(ThreadNode));
        T->data = ch;
        T->ltag = 0;
        T->rtag = 0;
        InitTree(T->lchild);
        InitTree(T->rchild);
    }
}

static void visit(ThreadNode *q) {
    if (q->lchild == nullptr) {        //左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != nullptr && pre->rchild == nullptr) {     //建立前驱节点的后续线索
        pre->rchild = q;
        pre->rtag = 1;
    }
    pre = q;
}


/*--------------------------先序线索--------------------------*/
//先序遍历二叉树，
void PreThread(ThreadTree T) {
    if (T != nullptr) {
        visit(T);
        if (T->ltag != 1)  //lchild不是前驱节点
            PreThread(T->lchild);
        if (T->rtag != 1)  //rchild不是后驱节点，因为回溯回来可能造成死循环
            PreThread(T->rchild);
    }
}

//建立先序线索化二叉树
void CreatPreThread(ThreadTree T) {
    pre = nullptr;
    if (T != nullptr) {
        PreThread(T);            //先序线索化二叉树
        if (pre->rchild == nullptr) {
            pre->rtag = 1;      //处理遍历的最后一个节点
        }
    }
}


/*先序线索二叉树中找先序后继*/
//找先序线索二叉树中节点p在先序序列下的后继
ThreadNode *Nextnode_Preorder(ThreadNode *p) {
    if (p->rtag == 0) {
        if (p->lchild != nullptr) return p->lchild;
        return p->rchild;
    }
    return p->rchild;   //rtag==1直接返回后继线索
}

//遍历线索二叉树
void Preorder(ThreadTree T) {
    for (ThreadNode *p = T; p != nullptr; p = Nextnode_Preorder(p)) {
        cout << p->data << " ";
    }
    cout << endl;
}
/*--------------------------中序线索--------------------------*/
//中序遍历二叉树，
void InThread(ThreadTree T) {
    if (T != nullptr) {
        InThread(T->lchild);
        visit(T);
        InThread(T->rchild);
    }
}

//建立中序线索化二叉树
void CreatInThread(ThreadTree T) {
    pre = nullptr;
    if (T != nullptr) {
        InThread(T);            //中序线索化二叉树
        if (pre->rchild == nullptr) {
            pre->rtag = 1;      //处理遍历的最后一个节点
        }
    }
}

/*中序线索二叉树中找中序后继*/
//找中序线索二叉树中中序序列下的第一个节点
static ThreadNode *Firstnode_Inorder(ThreadNode *p) {
    while (p->ltag == 0) p = p->lchild;           //最左下节点（不一定是叶节点）
    return p;
}

//找中序线索二叉树中节点p在中序序列下的后继
ThreadNode *Nextnode_Inorder(ThreadNode *p) {
    if (p->rtag == 0) return Firstnode_Inorder(p->rchild);
    return p->rchild;   //rtag==1直接返回后继线索
}

//遍历线索二叉树
void Inorder(ThreadTree T) {
    for (ThreadNode *p = Firstnode_Inorder(T); p != nullptr; p = Nextnode_Inorder(p)) {
        cout << p->data << " ";
    }
    cout << endl;
}

/*中序线索二叉树中找中序前驱*/
//找到以p为根的子树中，最后一个被中序遍历的节点
static ThreadNode *Lastnode_Inorder(ThreadNode *p) {
    //循环找到最右下节点（不一定是叶节点）
    while (p->rtag == 0) p = p->rchild;
    return p;
}

//在中序线索二叉树中找到节点p的前驱节点
ThreadNode *Prenode_Inorder(ThreadNode *p) {
    //左子树中最右下节点
    if (p->ltag == 0) return Lastnode_Inorder(p->lchild);
    return p->lchild;   //ltag==1直接返回前驱
}

//逆向遍历线索二叉树
void RevInorder(ThreadTree T) {
    for (ThreadNode *p = Lastnode_Inorder(T); p != nullptr; p = Prenode_Inorder(p)) {
        cout << p->data << " ";
    }
    cout << endl;
}

/*--------------------------后序线索--------------------------*/
//后序遍历二叉树，
void PostThread(ThreadTree T) {
    if(T!=nullptr){
        PostThread(T->lchild);
        PostThread(T->rchild);
        visit(T);
    }
}

//建立后序线索化二叉树
void CreatPostThread(ThreadTree T) {
    pre = nullptr;
    if (T != nullptr) {
        PostThread(T);            //先序线索化二叉树
        if (pre->rchild == nullptr) {
            pre->rtag = 1;      //处理遍历的最后一个节点
        }
    }
}

/*后序线索二叉树中找后序前驱*/
//找后序线索二叉树中节点p在后序序列下的前驱
ThreadNode *Prenode_Postorder(ThreadNode *p) {
    if(p->ltag == 0){
        if(p->rchild!=nullptr) return p->rchild;
        return p->lchild;
    }
    return p->lchild;   //ltag==1直接返回前驱线索
}

//逆向遍历线索二叉树
void RevPostorder(ThreadTree T){
    for(ThreadNode* p=T;p!=nullptr;p = Prenode_Postorder(p)){
        cout<<p->data<<" ";
    }
    cout<<endl;
}

/*输入
1
2
3
#
#
4
#
#
5
#
#
    */
void test() {
    //先序
    cout<<"PreOrder"<<endl;
    ThreadTree T;
    T = (ThreadNode *) malloc(sizeof(ThreadNode));
    InitTree(T);
    CreatPreThread(T);
    Preorder(T);
    //中序
    cout<<"InOrder"<<endl;
    T = (ThreadNode *) malloc(sizeof(ThreadNode));
    InitTree(T);
    CreatInThread(T);
    Inorder(T);
    RevInorder(T);
    //后序
    cout<<"PostOrder"<<endl;
    T = (ThreadNode *) malloc(sizeof(ThreadNode));
    InitTree(T);
    CreatPostThread(T);
    RevPostorder(T);
}

int main() {
    test();
    return 0;
}